package gold.gold02;

import java.util.*;
import java.util.concurrent.CopyOnWriteArraySet;

/**
 * 中等
 * 不知道java怎么对矩阵进行批量操作, 比如获取graph中第一个数字都为3的元素的集合。
 */
public class S0401节点间通路 {
    /**
     * 96, 节点数量太多, 肯定不能用二维数组存储了。
     * dfs 吧, 就要找出所有start可达的点
     * 因为节点的值刚好是0~n-1, 所以应该是可以遍历一遍解决的。
     */
    public boolean findWhetherExistsPathNew(int n, int[][] graph, int start, int target) {
        if(n == 0) return false;
        boolean[] arrive = new boolean[n];
        arrive[start] = true;
        // 哈哈哈哈
        for(int[] edge : graph){
            if(arrive[edge[0]])
                arrive[edge[1]] = true;
        }
        for(int[] edge : graph){
            if(arrive[edge[0]])
                arrive[edge[1]] = true;
        }
        return arrive[target];
    }


    // 广度优先, 超时了。
    public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
        Set<Integer> arrival = new CopyOnWriteArraySet<>();
        arrival.add(start);
        Set<Integer> tempArrival = new CopyOnWriteArraySet<>();
        tempArrival.add(start);
        while(true) {
            int count = arrival.size();
            List<Integer> tempArriList = new ArrayList<>(tempArrival); //可以直接这样从set变成list。
            Collections.sort(tempArriList);
            Iterator<Integer> arriIter = tempArriList.iterator();
            int posi = arriIter.next();
            for(int[] route: graph){
                if(route[0] > posi){
                    if(arriIter.hasNext()){
                        posi = arriIter.next();
                    }else {
                        break;
                    }
                }
                if(route[0]==posi){
                    tempArrival.add(route[1]);
                }
            }
            // 下一层深度中剔除上面已有的节点。一个addAll一个removeAll。
            tempArrival.addAll(arrival);
            tempArrival.removeAll(arrival);
            arrival.addAll(tempArrival);
            if(count == arrival.size()) break;
        }
        return arrival.contains(target);
    }

    /**
     * 深度优先和广度优先各留一个例子。以后再看。
     */
    boolean exist=false;
    public boolean findWhetherExistsPath2(int n, int[][] graph, int start, int target) {
        LinkedList<Integer>[] adjTable=new LinkedList[n];
        for(int i=0;i<n;i++){
            adjTable[i]=new LinkedList<>();
        }
        for(int i=0;i<graph.length;i++){
            int from=graph[i][0];
            int to=graph[i][1];
            adjTable[from].add(to);
        }
        int[] visited=new int[n];
        dfs(start,target,adjTable,visited);
        return exist;
    }
    public void dfs(int start,int target,LinkedList<Integer>[] adjTable, int[] visited){
        visited[start]=1;
        if(start==target){
            exist=true;
        }
        Iterator<Integer> iter=adjTable[start].iterator();
        while(iter.hasNext()){
            int temp = iter.next();
            if(visited[temp]==0){
                dfs(temp,target,adjTable,visited);
            }
        }
    }
    public boolean findWhetherExistsPath3(int n, int[][] graph, int start, int target) {
        LinkedList<Integer>[] adjTable=new LinkedList[n];
        for(int i=0;i<n;i++){
            adjTable[i]=new LinkedList<>();
        }
        for(int i=0;i<graph.length;i++){
            int from=graph[i][0];
            int to=graph[i][1];
            adjTable[from].add(to);
        }
        int[] visited=new int[n];
        return bfs(start,target,adjTable,visited);
    }
    public boolean bfs(int start,int target,LinkedList<Integer>[] adjTable,int[] visited){
        if(start==target){
            return true;
        }
        Deque<Integer> que=new LinkedList<>();
        que.add(start);
        visited[start]=1;
        while(!que.isEmpty()){
            int p=que.remove();
            Iterator<Integer> iter=adjTable[p].iterator();
            while(iter.hasNext()){
                int temp=iter.next();
                if(visited[temp]==0){
                    if(temp==target){
                        return true;
                    }else{
                        que.add(temp);
                        visited[temp]=1;
                    }
                }
            }
        }
        return false;
    }
    public static void main(String[] args) {
        int[][] graph = {{0, 1}, {0, 2}, {0, 4}, {0, 4}, {0, 1}, {1, 3}, {1, 4}, {1, 3}, {2, 3}, {3, 4}};
        System.out.println(new S0401节点间通路().findWhetherExistsPath(5, graph, 0, 4));
    }
}
